package com.it.data_tree.tree.binarySearchTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: CaoYouGen
 * @DateTime: 2023/04/17/12:20
 * @注释: 搜索二叉树 树节点类
 **/
public class BSTTree {
    public BSTNode root;
    
    /**
     * @param root:
     * @return void
     * @作者: Coke
     * @注释: 层序遍历打印树结构
     * @DateTime: 2023/4/22 20:40
     */
    public static void printTree (BSTNode root) {
        if (root == null) {
            return;
        }
        
        Queue<BSTNode> queue = new LinkedList<>();
        Queue<BSTNode> queue2 = new LinkedList<>();
        queue.offer(root);
        queue2.offer(root);
        
        while (! queue.isEmpty()) {
            int size = queue.size();
            int size2 = queue.size();
            
            for (int i = 0; i < size; i++) {
                BSTNode node = queue.poll();
                String valueString = String.format("%-4s", node.key + "" + node.value); // 格式化节点值的输出
                
                System.out.print(valueString);
                
                if (node.left != null) {
                    queue.offer(node.left);
                } else {
                    System.out.print("   ");
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                } else {
                    System.out.print("   ");
                }
            }
            
            System.out.println();
            
            for (int i = 0; i < size2; i++) {
                BSTNode node2 = queue2.poll();
                
                if (node2.left != null) {
                    queue2.offer(node2.left);
                    System.out.print(" / ");
                } else {
                    System.out.print("   ");
                }
                
                if (node2.right != null) {
                    queue2.offer(node2.right);
                    System.out.print("\\ ");
                } else {
                    System.out.print("   ");
                }
            }
            
            System.out.println();
        }
    }
    
    /**
     * @param key: 查找的关键字
     * @return Object 关键字对应的值
     * @Author: CaoYouGen
     * @注释: 查找关键字对应的值
     * @DateTime: 2023/4/17 12:22
     */
    public Object get (int key) {
        return doGet(root, key);
    }
    
    /**
     * @param node: 查找的树
     * @param key:  查找的关键字
     * @return Object 关键字对应的值
     * @Author: CaoYouGen
     * @注释: 查找关键字 - 实现逻辑
     * @DateTime: 2023/4/17 12:39
     */
    private Object doGet (BSTNode node, int key) {
        if (node == null) {
            return null;
        }
        // 向左找
        if (node.key > key) {
            return doGet(node.left, key);
            // 向右找
        } else if (node.key < key) {
            return doGet(node.right, key);
            // 找到了
        } else {
            return node.value;
        }
    }
    
    /**
     * @return Object 最小关键字对应的值
     * @Author: CaoYouGen
     * @注释: 查找最小关键字对应的值
     * @DateTime: 2023/4/17 12:23
     */
    public Object min () {
        return doMin(root);
    }
    
    /**
     * @param node:
     * @return Object
     * @Author: CaoYouGen
     * @注释: 查找最小关键字对应的值
     * @DateTime: 2023/4/19 12:34
     */
    private Object doMin (BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.value;
        }
        return doMin(node.left);
    }
    
    /**
     * @return Object 最大关键字对应的值
     * @Author: CaoYouGen
     * @注释: 查找最大关键字对应的值
     * @DateTime: 2023/4/17 12:24
     */
    public Object max () {
        return doMan(root);
    }
    
    /**
     * @param node:
     * @return Object
     * @Author: CaoYouGen
     * @注释: 查找最大关键字对应的值
     * @DateTime: 2023/4/19 12:47
     */
    private Object doMan (BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.value;
        }
        return doMan(node.right);
    }
    
    /**
     * @param key:   存储的关键字
     * @param value: 存储的值
     * @return void
     * @Author: CaoYouGen
     * @注释: 存储关键字和对应值
     * @DateTime: 2023/4/17 12:26
     */
    public void put (int key, Object value) {
        // 1. 先查找在添加 情况一：key 存在  更新操作  情况二：key不存在  新增操作
        BSTNode node = root;
        BSTNode parent = null; // 用于记录 node 的父节点
        while (node != null) {
            parent = node;
            // 向左查找
            if (key < node.key) {
                node = node.left;
                // 向右查找
            } else if (key > node.key) {
                node = node.right;
                // key 相等 找到了 (执行更新操作)
            } else {
                node.value = value;
                return;
            }
        }
        // 循环结束 没有找到 （新增操作）
        // 没有树 新增节点为根节点
        if (parent == null) {
            root = new BSTNode(key, value);
            // 向左新增节点
        } else if (key < parent.key) {
            parent.left = new BSTNode(key, value);
            // 向右新增节点
        } else if (key > parent.key) {
            parent.right = new BSTNode(key, value);
        }
    }
    
    /**
     * @param key: 关键字
     * @return Object  前驱值
     * @Author: CaoYouGen
     * @注释: 查找关键字的前驱值
     * @DateTime: 2023/4/17 12:29
     */
    public Object successor (int key) {
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                parent = node;
                node = node.right;
            } else {
                // 找到了
                break;
            }
        }
        if (node == null) {
            return null;
        }
        // 找到节点 情况一：有左子节点，此时左子节点的最大值就是前驱值
        if (node.left != null) {
            return doMin(node.left);
        }
        // 找到节点 情况二：没有左子节点 ，找自左而来最近的祖先就是前任
        return parent;
    }
    
    /**
     * @param key: 关键字
     * @return Object 后继值
     * @Author: CaoYouGen
     * @注释: 查找关键字的后继值
     * @DateTime: 2023/4/17 12:30
     */
    public Object predecessor (int key) {
        BSTNode node = root;
        BSTNode parent = null; // 用于记录祖先节点
        while (node != null) {
            if (key < node.key) {
                parent = node;
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                // 找到了
                break;
            }
        }
        if (node == null) {
            return null;
        }
        // 找到节点 情况一：有右子节点，此时右子节点的最小值就是前驱值
        if (node.right != null) {
            return doMin(node.right);
        }
        // 找到节点 情况二：没有右子节点 ，找自右而来最近的祖先就是前任
        return parent;
    }
    
    /**
     * @param key: 关键字
     * @return Object 被删除关键字对应值
     * @Author: CaoYouGen
     * @注释: 根据关键字删除 (非递归)
     * @DateTime: 2023/4/17 12:31
     */
    public Object delete (int key) {
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            if (key < node.key) {
                parent = node;
                node = node.left;
            } else if (key > node.key) {
                parent = node;
                node = node.right;
            } else {
                // 找到了
                break;
            }
        }
        if (parent == null && node.key != key) {
            return null;
        }
        // 删除操作 （共四种情况）===> 其中情况三：删除节点为叶子节点没有左右节点可以走情况一或者情况二的逻辑
        // 情况一 删除节点没有左子节点，将右节点托孤给parent
        if (node.left == null) {
            shift(parent, node, node.right);
            // 情况二 删除节点没有右子节点，将左节点托孤给parent
        } else if (node.right == null) {
            shift(parent, node, node.left);
        } else {
            // 情况四 删除节点既有左子节点又有右子节点
            // 4.1 被删除节点找后继（右节点中的最小值）
            BSTNode rightMinNode = node.right;
            BSTNode parentByMin = node; // 后继的父节点
            while (rightMinNode.left != null) {
                parentByMin = rightMinNode;
                rightMinNode = rightMinNode.left;
            }
            
            // 4.2 被删除节点与后继节点不相邻，处理后继的后事（只有右子节点）
            if (node != parentByMin) {
                shift(parentByMin, rightMinNode, rightMinNode.right);
                rightMinNode.right = node.right;
            }
            // 4.3 后继节点取代删除节点
            shift(parent, node, rightMinNode);
            rightMinNode.left = node.left;
        }
        return node;
    }
    
    /**
     * @param key: 删除节点的关键值
     * @return Object  被删除的节点
     * @作者: Coke
     * @注释: 根据关键字删除 (递归)
     * @DateTime: 2023/4/22 20:42
     */
    public Object delete2 (int key) {
        ArrayList<Object> result = new ArrayList<>();
        root = doDelete2(root, key, result);
        return result;
    }
    
    /**
     * @param node: 删除节点的起点
     * @param key:  删除节点的关键值
     * @return BSTNode  删除节点的子节点
     * @作者: Coke
     * @注释: 根据关键字删除 (递归)  执行逻辑
     * @DateTime: 2023/4/22 21:10
     */
    private BSTNode doDelete2 (BSTNode node, int key, ArrayList<Object> result) {
        if (node == null) {
            return null;
        }
        // 向左找
        if (key < node.key) {
            // 返回的是删除节点的子节点
            node.left = doDelete2(node.left, key, result);
            return node;
        }
        // 向右找
        if (key > node.key) {
            // 返回的是删除节点的子节点
            node.right = doDelete2(node.right, key, result);
            return node;
        }
        // 找到了
        result.add(node);
        // 1. 情况一  只有右子节点
        if (node.left == null) {
            return node.right;
        }
        // 2. 情况二 只有在子节点
        if (node.right == null) {
            return node.left;
        }
        // 3. 情况三 有两个孩子 （先找后继节点）
        BSTNode n = node.right;
        while (n.left != null) {
            n = n.left;
        }
        
        // 处理后继节点的子节点
        n.right = doDelete2(node.right, n.key, new ArrayList<>());
        n.left = node.left;
        return n;
    }
    
    /**
     * @param parent:  被删除节点的父节点
     * @param deleted: 被删除节点
     * @param child:   被顶上去的节点（被删除节点的子节点）
     * @return void
     * @作者: Coke
     * @注释: 托孤方法
     * @DateTime: 2023/4/22 16:26
     */
    public void shift (BSTNode parent, BSTNode deleted, BSTNode child) {
        // 如果父节点为null （当前节点为父节点）
        if (parent == null) {
            root = child;
            // 删除节点在左边
        } else if (deleted == parent.left) {
            parent.left = child;
            // 删除节点在右边
        } else {
            parent.right = child;
        }
    }
    
    
    /**
     * @param key: 传入的key
     * @return List<Object> 返回比传入key小的值的集合
     * @作者: Coke
     * @注释: 找比key小的值
     * @DateTime: 2023/4/23 21:47
     */
    public List<Object> less (int key) {
        // 存储比key小的值
        ArrayList<Object> list = new ArrayList<>();
        //  记录经过的节点
        LinkedList<BSTNode> stack = new LinkedList<>();
        BSTNode node = root;
        while (node != null || ! stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                // 处理值
                BSTNode pop = stack.pop();
                if (pop.key < key) {
                    list.add(pop.key);
                } else {
                    break;
                }
                node = pop.right;
            }
        }
        return list;
    }
    
    /**
     * @param key: 传入的key
     * @return List<Object>  返回比传入key大的值的集合
     * @作者: Coke
     * @注释: 找比key大的值
     * @DateTime: 2023/4/23 22:14
     */
    public List<Object> greater (int key) {
        // 存储结果的集合
        ArrayList<Object> list = new ArrayList<>();
        // 临时存储路径节点的栈
        LinkedList<BSTNode> stack = new LinkedList<>();
        BSTNode node = root;
        while (node != null || ! stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.right;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key > key) {
                    list.add(pop.key);
                } else {
                    break;
                }
                node = pop.left;
            }
        }
        return list;
    }
    
    
    /**
     * @param minKey: 传入的较小key
     * @param maxKey: 传入的较大key
     * @return List<Object>  返回比传入 比minKey大 比maxKey小 的值的集合
     * @作者: Coke
     * @注释: 找minKey - maxKey 之间的值
     * @DateTime: 2023/4/23 22:22
     */
    public List<Object> between (int minKey, int maxKey) {
        // 存储结果的集合
        ArrayList<Object> list = new ArrayList<>();
        // 临时存储路径节点的栈
        LinkedList<BSTNode> stack = new LinkedList<>();
        BSTNode node = root;
        while (node != null || ! stack.isEmpty()) {
            if (node != null) {
                // 压栈
                stack.push(node);
                node = node.left;
            } else {
                // 弹栈
                BSTNode pop = stack.pop();
                if (pop.key >= minKey && pop.key <= maxKey) {
                    list.add(pop.key);
                } else if (pop.key > maxKey) {
                    break;
                }
                node = pop.right;
            }
        }
        return list;
    }
    
    
    /**
     * @return void
     * @作者: Coke
     * @注释: 层序遍历树
     * @DateTime: 2023/4/19 21:53
     */
    public void print () {
        Queue<BSTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (! queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                BSTNode node = queue.poll();
                System.out.print(node.key + " " + node.value + "\t");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            System.out.println();
        }
    }
}